//
// Description: 873. 欧拉函数
// Created by Loading on 2022/5/25.
//

/* 在数论，对正整数n，欧拉函数是小于n的正整数中与n互质的数的个数。对于互质，如果a和b的最大公约数为1，则a和b互质 */

/*
 * 一个正整数 N 一定可以表示成 N = p1^c1 * p2^c2 * ... * pk^ck，其中 p1、p2 …… pk 均为质数
 * 欧拉函数的具体公式：ϕ(n) = n * (1 - 1/p1) * (1 - 1/p2) * …… * （1 - 1/pk)
 *
 * eg. 1~5中与6互质的数为1和5两个，质因子为2和3，带入欧拉函数公式，ϕ(6) = 6 * (1 - 1/2) * (1 - 1/3) = 2
 */

#include <bits/stdc++.h>

using namespace std;

int euler(int n) {
    int res = n;

    // 分解质因子
    for (int i = 2; i <= n / i; ++i) {
        if (n % i == 0) {
            // 防止越界和 1 / i 的结果错误运算，不能使用 res = res * (1 - 1 / i)
            res = res / i * (i - 1);
            while (n % i == 0) {
                n /= i;
            }
        }
    }
    if (n > 1) {
        res = res / n * (n - 1);
    }

    return res;
}

int main() {
    int n;
    cin >> n;
    while (n--) {
        int a;
        cin >> a;

        cout << euler(a) << endl;
    }

    return 0;
}